package com.breeze.leetcode;

import com.breeze.utils.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
 * 145. 二叉树的后序遍历
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
public class LeetCode145 {
    static class Solution {
        /**
         * 方法1:递归
         * 时间复杂度:O(n) 其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
         * 空间复杂度:O(logn) 为递归过程中栈的开销，平均情况下为 O(log n),最坏情况下树呈现链状，为 O(n)
         */
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            postorder(root, res);
            return res;
        }

        private void postorder(TreeNode root, List<Integer> res) {
            if (root == null) {
                return;
            }
            postorder(root.left, res);
            postorder(root.right, res);
            res.add(root.val);
        }

        /**
         * 方法2：迭代
         */
        public List<Integer> postorderTraversal1(TreeNode root) {
            List<Integer> reverseRes = new LinkedList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode temp = root;
            while (temp != null || !stack.isEmpty()) {
                if (temp.left != null) {
                    stack.push(temp.left);
                }
                reverseRes.add(temp.val);
                temp = temp.right;
                if (temp == null && !stack.isEmpty()) {
                    temp = stack.pop();
                }
            }
            List<Integer> res = new LinkedList<>();
            for (int i = reverseRes.size() - 1; i >= 0; i--) {
                res.add(reverseRes.get(i));
            }
            return res;
        }

        /**
         * 迭代优化
         */
        public List<Integer> postorderTraversal2(TreeNode root) {
            List<Integer> reverseRes = new LinkedList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode temp = root;
            while (temp != null || !stack.isEmpty()) {
                if (temp.left != null) {
                    stack.push(temp.left);
                }
                reverseRes.add(temp.val);
                temp = temp.right;
                if (temp == null && !stack.isEmpty()) {
                    temp = stack.pop();
                }
            }
            List<Integer> res = new LinkedList<>();
            for (int i = reverseRes.size() - 1; i >= 0; i--) {
                res.add(reverseRes.get(i));
            }
            return res;
        }
    }
}
